The International Telecommunications Union (ITU, formerly the CCITT) and the International Organization for Standardization (ISO) have promulgated a series of joint recommendations to standardize a seven-layer OSI protocol model to allow the communication of application data among heterogeneous computers in a uniform manner. The seven layers comprise a physical layer, a data link layer, a network layer, a transport layer, a session layer, a presentation layer, and an application layer.
These recommendations include the specification of Abstract Syntax Notation One (ASN.1), a standardized notation for describing application layer data structures. ASN.1 is documented in ISO 8824 .vertline. CCITT Rec. X.208, later revised in ISO 8824-1 and ITU-T Recs. X.680 through X.683. A set of data types expressed in ASN.1 is called an abstract syntax, and it structures the communication of information between two systems at the application layer. The syntax is abstract because it is independent of its physical representation in a real system. In order to be communicated, an abstract syntax datum must be translated into a transfer syntax having a specific physical representation, which is then presented to the presentation layer for transport to the remote system. A discrete unit of encoded information is called a protocol data unit (PDU). This translation process is called encoding. On the remote system, the inverse process, decoding, takes place when the presentation layer presents an incoming PDU to the application layer, which decodes it into the abstract syntax.
The joint ITU-T/ISO recommendations also include a series of encoding rules for transforming abstract data syntaxes expressed in ASN.1 into transfer syntax suitable for communication between OSI protocol machines. Data exchange agreements expressed using ASN.1, when implemented in software using the specified encoding rules to present the data to an OSI protocol machine, allow successful interoperation between different types of computers across a network. The encoding rules are specified in ISO 8825 .vertline. CCITT Rec. X.209, later revised in ISO 8825-1 and ITU-T Recs. X.690 through X.691.
Systems based on ASN.1 data exchange agreements are being deployed widely in the telecommunications industry, where the standard was pioneered, and other industries, including aviation and electronic commerce. For example, ASN.1 is used for avionics control in the Boeing 777, in ground-to-air communications systems, and the secure electronic transaction standard for Mastercard and VISA. While designed for data communication, the method is also suitable for data storage. For example, the National Institute of Health is using ASN.1 to specify storage of human genome data on CD-ROM.
The prior art includes a variety of methods for implementing the ASN.1 encoding rules. Some of these methods involve the translation of data directed by metadata, that is, auxiliary data that describes the structure of the data itself. One example is that described in Anezaki et al., U.S. Pat. No. 5,418,963. Other methods involve an ASN.1 compilation process that generates software routines to translate particular ASN.1 data types, such as the Retix ASN.1 Compiler (sold by Retix Corporation of Santa Monica, Calif.) or the OSS ASN.1 Compiler (sold by Open Systems Solutions, Inc., of Princeton, N.J.).
However, none of the prior art systems employ a consolidated method capable of supporting a variety of output forms for the encoding. In many cases, the encoding methods require the output to be packaged into a contiguous block of pre-allocated memory (e.g., Anezaki). This mechanism has two notable limitations. The first is that the application is burdened with the task of pre-determining an appropriate amount of memory to store the PDU and of pre-allocating the memory. The second is that if the application ultimately needs to present the PDU in a form other than contiguous memory (e.g., disk file, socket, or other data structure), then it is forced to encode the pre-allocated block of data back into memory, and then copy it out of memory into the ultimate presentation medium. This two pass process is inefficient, requiring more computing resources and taking more time.
Consequently, it is desirable to create an open-ended encoding/decoding technique that directly supports a variety of output forms, avoiding the need for additional application processing. It is further desirable to permit encoding without the need to predetermine the size of the memory block.
The present invention builds upon two prior-art general programming techniques, template functions and iterator interfaces. Both were developed and used for different applications. A template function is a technique first introduced in the mid-1980's in programming languages such as Ada and C++. The template mechanism allows a function, class or package to be defined leaving one or more necessary parameterized type definition unspecified until it is compiled. The source code that implements the template function uses the parameterized type and makes various assumptions about it, but the parameterized type is otherwise unknown to the function implementation. When the template function is used in application source code, the template parameters are filled in with particular types. Any type may be used, provided it meets the requirements of the implementation. For example, an implementation may require the parameterized type to support addition and multiplication operations. In this case, the parameter may be filled in by any integer, floating point type, or other user-defined type that supports addition and multiplication.
Iterator interfaces are a logical extension to the standard use of templates. They exist in various C++ standard libraries, most notably the Standard Template Library (STL) originally promulgated by Hewlett-Packard, which is now being adopted as part of the ANSI Standard for C++. As discussed above, the implementation imposes requirements on the types which may fill in its parameters, depending on the assumptions made in the implementation. The purpose of iterator interfaces is to standardize and classify the sorts of assumptions made by implementations to facilitate a consistent and coherent use among a library of related templates. This eliminates redundancy that would otherwise exist between various templates. In STL, a taxonomy of iterators is defined, with a standard set of assumptions associated with each type of iterator. Assumptions are arranged progressively, such that all iterators support a base set of assumptions, and higher forms of iterators may support additional assumptions.
For example, basic iterators may be either "forward" or "backward" iterators, meaning that they may access one element at a time in one direction only. Forward iterators support the "++" operator, and backward iterators support the "--" operator. Bi-directional iterators support both forward and backward operations. Random access iterators support all bi-directional operations, and they allow access of indexed elements (via the "[]" operator). The definition of these interfaces facilitates the creation of "containers," which are template classes that provide iterator interfaces, and "algorithms," template functions that operate on containers.